package main

import (
	"fmt"
)

func main() {

	numbers := []int{14, 33, 27, 10, 35, 19, 42, 44}
	fmt.Printf("%v\n", numbers)
	MergeSortOpt(0, len(numbers)-1, numbers)
	fmt.Printf("%v\n", numbers)

}

func MergeSortOpt(lo, hi int, numbers []int) {

	if lo < hi {
		mid := (lo + hi) / 2
		MergeSortOpt(lo, mid, numbers)
		MergeSortOpt(mid+1, hi, numbers)
		MergeOpt(lo, mid, hi, numbers)
	} else {
		return
	}

}

func MergeOpt(lo, mid, hi int, numbers []int) {

	loIndex := lo
	hiIndex := mid
	merged := []int{}
	for {
		if loIndex < mid && hiIndex <= hi {
			if numbers[loIndex] < numbers[hiIndex] {
				merged = append(merged, numbers[loIndex])
				loIndex++
			} else {
				merged = append(merged, numbers[hiIndex])
				hiIndex++
			}
		} else if loIndex < mid {
			//array1 单独存在元素
			merged = append(merged, numbers[loIndex])
			loIndex++
		} else if hiIndex <= hi {
			//array2 单独存在元素
			merged = append(merged, numbers[hiIndex])
			hiIndex++
		}

		if loIndex >= mid && hiIndex > hi {
			break
		}
	}

	for i, num := range merged {
		numbers[i+lo] = num
	}

}
